/**
 * @author 雷明浩
 * @date 2025/5/30 15:01
 */
public class BuildTree {
    // leetcode 从前序与中序遍历序列构造二叉树
    // https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/?envType=study-plan-v2&envId=top-100-liked
    private int index;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        index = 0;
        return buildTreeChild(preorder, inorder, 0, preorder.length-1);
    }

    private TreeNode buildTreeChild(int[] preorder, int[] inorder, int left, int right) {
        if (left > right) {
            return null;
        }
        int pivot = findPivot(inorder, left, right, preorder[index]);
        TreeNode newNode = new TreeNode(preorder[index++]);
        newNode.left = buildTreeChild(preorder, inorder, left, pivot-1);
        newNode.right = buildTreeChild(preorder, inorder, pivot+1, right);
        return newNode;
    }

    private int findPivot(int[] inorder, int left, int right, int target) {
        for (int i = left; i <= right; i++) {
            if (inorder[i] == target) {
                return i;
            }
        }
        return -1;
    }
}